package com.jjw.route.algorithm;

import com.baomidou.mybatisplus.core.conditions.query.LambdaQueryWrapper;
import com.baomidou.mybatisplus.core.toolkit.Wrappers;
import com.jjw.route.dao.PoiDao;
import com.jjw.route.entity.PoiEntity;
import com.jjw.route.entity.PplengthEntity;
import com.jjw.route.service.PoiService;
import com.jjw.route.service.PplengthService;
import com.jjw.route.to.SpotPlanTo;
import com.jjw.route.vo.PlanResultVo;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;

@Slf4j
@Service
public class RouteGetAlgorithm {
    @Autowired
    private PoiService poiService;
    @Autowired
    private PplengthService pplengthService;
    private ArrayList<PoiEntity> myRoute;

    public PlanResultVo getPlan(SpotPlanTo spotPlanTo) {
        // 获取起始数据
        ArrayList<String> spotsString = spotPlanTo.getSpots();
        String originString = spotPlanTo.getOrigin();
        String destinationString = spotPlanTo.getDestination();
        List<PoiEntity> poiEntities = poiService.selectByNameList(spotsString);
        PoiEntity origin = poiService.selectByName(originString);
        PoiEntity destination = poiService.selectByName(destinationString);


        int maxPOIs = spotPlanTo.getMaxPOIs();
        int budgetTime = spotPlanTo.getBudgetTime();
        int stayOfTime = 30;

        ArrayList<ArrayList<PoiEntity>> myRoutes = combination(poiEntities);
        //将景点（POIs）按照去的先后顺序排列组合，得到不同的路线（由于起止点可以不一样，故使用全排列的方式；若起止点一样，则可以使用组合的方式）
        int costTime = costOfTime(origin, destination, myRoutes);
        float[] rectangle = findZone(origin, destination, myRoute);;
        ArrayList<PoiEntity> newPOIs = function2(rectangle);
        while (myRoute.size() < maxPOIs && addNewPOI(costTime, budgetTime, stayOfTime)) {
//            rectangle = findZone(origin, destination, myRoute);
            if (newPOIs.size() == 0) {
                break;
            } else {
                myRoutes = insertToCombination(myRoute, newPOIs.remove(0));
                costTime = costOfTime(origin, destination, myRoutes);
            }
        }
        myRoute.add(0, origin);
        myRoute.add(myRoute.size(), destination);
        PlanResultVo planResultVo = new PlanResultVo();
        ArrayList<Integer> costs = new ArrayList<>();
        for(int i = 0; i < myRoute.size() - 1; i++) {
            costs.add(Math.toIntExact((getCostTime(myRoute.get(i), myRoute.get(i + 1)) / 60)));
        }
        planResultVo.setSpotInfos(myRoute);
        return planResultVo;
    }


    private float getDistance(float latitude1, float latitude2, float longitude1, float longitude2) {
        return (latitude1 - latitude2)*(latitude1 - latitude2) + (longitude1 - longitude2) * (longitude1 - longitude2);
    }
    private int costOfTime(PoiEntity origin, PoiEntity destination, ArrayList<ArrayList<PoiEntity>> myRoutes) {
        int total_duration = 0;
        ArrayList<Integer> costs = new ArrayList<>();
        int in = myRoutes.size();
        for (int i = 0; i < in; i++) {

            int costTime = getCostTime(origin, myRoutes.get(i).get(0));
            total_duration += costTime;

            int jn = myRoutes.get(i).size();
            for (int j = 0; j < jn - 1; j++) {
                costTime = getCostTime(myRoutes.get(i).get(j), myRoutes.get(i).get(j + 1));
                total_duration += costTime;
            }
            costTime = getCostTime(myRoutes.get(i).get(jn - 1), destination);
            total_duration += costTime;
            costs.add(total_duration);
            total_duration = 0;
        }
        int minIndex = costs.indexOf(Collections.min(costs));
//        Collections.copy(myRoute, myRoutes.get(minIndex));//!!!
        myRoute = new ArrayList<>(myRoutes.get(minIndex));
        // 加上需要在每个景点带的时间
        int stayTime = 0;
        for(PoiEntity spotInfo : myRoute) {
            stayTime += 30;
        }
        return costs.get(minIndex) + stayTime;
    }

    /**
     * 得到一个最小矩形，能够框住当前的路线
     *
     * @param origin-开始地点
     * @param destination-结束地点
     * @param spots-路线中的各个节点
     * @return 返回两个坐标，矩形左上角和右下角
     */
    private float[] findZone(PoiEntity origin, PoiEntity destination, ArrayList<PoiEntity> spots) {
        float minX, maxX, minY, maxY;
        minX = Math.min(Float.parseFloat(origin.getLatitude()), Float.parseFloat(destination.getLatitude()));
        maxX = Math.max(Float.parseFloat(origin.getLatitude()), Float.parseFloat(destination.getLatitude()));
        minY = Math.min(Float.parseFloat(origin.getLongitude()), Float.parseFloat(destination.getLongitude()));
        maxY = Math.max(Float.parseFloat(origin.getLongitude()), Float.parseFloat(destination.getLongitude()));

        for (PoiEntity cur : spots) {
            minX = Math.min(minX, Float.parseFloat(cur.getLatitude()));
            maxX = Math.max(maxX, Float.parseFloat(cur.getLatitude()));
            minY = Math.min(minY, Float.parseFloat(cur.getLongitude()));
            maxY = Math.max(maxY, Float.parseFloat(cur.getLongitude()));
        }
        return new float[]{minX, minY, maxX, maxY};
    }


    private ArrayList<ArrayList<PoiEntity>> insertToCombination(ArrayList<PoiEntity> myroute, PoiEntity newSpotInfo) {
        ArrayList<ArrayList<PoiEntity>> res = new ArrayList<>();

        for (int i = 0; i < myroute.size() + 1; i++) {
            myroute.add(i, newSpotInfo);
            res.add(new ArrayList<>(myroute));
            myroute.remove(i);
        }
        return res;
    }

    private ArrayList<ArrayList<PoiEntity>> combination(List<PoiEntity> spots) {
        ArrayList<ArrayList<PoiEntity>> res = new ArrayList<>();
        int[] is_visited = new int[spots.size()];
        ArrayList<PoiEntity> queue = new ArrayList<PoiEntity>();

        dfs(spots, spots.size(), is_visited, res, 0, queue);
        return res;
    }

    private Boolean addNewPOI(int curCost, int budgetTime, int maxStayTime) {
        if (budgetTime - curCost > maxStayTime)
            return Boolean.TRUE;
        else
            return Boolean.FALSE;
    }

    private static void dfs(List<PoiEntity> spots, int maxLength, int[] isVisited, ArrayList<ArrayList<PoiEntity>> res, int depth, ArrayList<PoiEntity> path) {
        if (depth == maxLength) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < maxLength; i++) {
            if (isVisited[i] == 0) {
                path.add(spots.get(i));
                isVisited[i] = 1;
                dfs(spots, maxLength, isVisited, res, depth + 1, path);
                path.remove(path.size() - 1);
                isVisited[i] = 0;
            }
        }
    }


    /**
     * 得到两个景点得通勤时间
     * @param spotA
     * @param spotB
     * @return
     */
    private int getCostTime(PoiEntity spotA, PoiEntity spotB) {
        return pplengthService.selectPpLength(Math.max(spotA.getId(), spotB.getId()), Math.min(spotA.getId(), spotB.getId()));
    }

    /**
     * 得到该矩形内所有景点
     * @param rectangle
     * @return
     */
    private ArrayList<PoiEntity> function2(float[] rectangle) {
        //minX, minY, maxX, maxY
        LambdaQueryWrapper<PoiEntity> wrapper = Wrappers.<PoiEntity>lambdaQuery()
                .notBetween(PoiEntity::getLatitude, rectangle[0],rectangle[2])
                .and(wrapper1 ->{
                    wrapper1.notBetween(PoiEntity::getLongitude, rectangle[1], rectangle[3]);
                });
        List<PoiEntity> spotInfos = poiService.selectList(wrapper);
        return new ArrayList<>(spotInfos);
    }
}
